#include <cstddef>
#include <cstdlib>
#include <new>

#pragma pack(push, 1)
struct BlockHeader
{
    size_t size;      // 当前块的总大小，包括头部
    size_t prev_size; // 前一个块的总大小
    bool is_free;
};

struct FreeBlock
{
    BlockHeader header;
    FreeBlock *next;
    FreeBlock *prev;
};
#pragma pack(pop)

class MemoryPool
{
public:
    MemoryPool(size_t size)
    {
        m_poolSize = size;
        m_pool = static_cast<char *>(malloc(size));
        if (!m_pool)
            throw std::bad_alloc();

        FreeBlock *init_block = reinterpret_cast<FreeBlock *>(m_pool);
        init_block->header.size = size;
        init_block->header.prev_size = 0;
        init_block->header.is_free = true;
        init_block->next = nullptr;
        init_block->prev = nullptr;
        m_freeList = init_block;
    }

    ~MemoryPool()
    {
        free(m_pool);
    }

    void *allocate(size_t size)
    {
        if (size == 0 || !m_pool)
            return nullptr;

        // 对齐到8字节
        size = (size + 7) & ~7;
        const size_t required_size = size + sizeof(BlockHeader);

        FreeBlock *block = findFreeBlock(required_size);
        if (!block)
            return nullptr;

        // 检查是否需要分割块
        if (block->header.size >= required_size + sizeof(FreeBlock))
        {
            splitBlock(block, required_size);
        }
        else
        {
            removeFromFreeList(block);
        }

        block->header.is_free = false;
        return reinterpret_cast<char *>(block) + sizeof(BlockHeader);
    }

    void deallocate(void *ptr)
    {
        if (!ptr || !m_pool)
            return;

        BlockHeader *header = reinterpret_cast<BlockHeader *>(static_cast<char *>(ptr) - sizeof(BlockHeader));
        header->is_free = true;

        mergeForward(header);  // 合并后方的块
        mergeBackward(header); // 合并前方的块

        // 添加合并后的块到空闲链表
        addToFreeList(reinterpret_cast<FreeBlock *>(header));
    }

private:
    char *m_pool;
    size_t m_poolSize;
    FreeBlock *m_freeList;

    FreeBlock *findFreeBlock(size_t size)
    {
        FreeBlock *current = m_freeList;
        while (current)
        {
            if (current->header.size >= size)
            {
                return current;
            }
            current = current->next;
        }
        return nullptr;
    }

    void splitBlock(FreeBlock *block, size_t size)
    {
        const size_t remaining = block->header.size - size;
        block->header.size = size;
        block->header.is_free = false;

        // 创建新块头
        BlockHeader *new_header = reinterpret_cast<BlockHeader *>(reinterpret_cast<char *>(block) + size);
        new_header->size = remaining;
        new_header->prev_size = size;
        new_header->is_free = true;

        // 更新后方块的prev_size
        BlockHeader *next_header = nextBlock(new_header);
        if (isValidBlock(next_header))
        {
            next_header->prev_size = new_header->size;
        }

        // 将新块添加到空闲链表
        addToFreeList(reinterpret_cast<FreeBlock *>(new_header));
        removeFromFreeList(block);
    }

    void mergeForward(BlockHeader *header)
    {
        BlockHeader *next = nextBlock(header);
        if (isValidBlock(next) && next->is_free)
        {
            removeFromFreeList(reinterpret_cast<FreeBlock *>(next));
            header->size += next->size;
            BlockHeader *new_next = nextBlock(header);
            if (isValidBlock(new_next))
            {
                new_next->prev_size = header->size;
            }
        }
    }

    void mergeBackward(BlockHeader *header)
    {
        if (header->prev_size == 0)
            return;

        BlockHeader *prev = prevBlock(header);
        if (isValidBlock(prev) && prev->is_free)
        {
            removeFromFreeList(reinterpret_cast<FreeBlock *>(prev));
            removeFromFreeList(reinterpret_cast<FreeBlock *>(header));
            prev->size += header->size;
            BlockHeader *new_next = nextBlock(prev);
            if (isValidBlock(new_next))
            {
                new_next->prev_size = prev->size;
            }
            header = prev; // 更新当前块为合并后的块
        }
    }

    BlockHeader *nextBlock(BlockHeader *header) const
    {
        return reinterpret_cast<BlockHeader *>(reinterpret_cast<char *>(header) + header->size);
    }

    BlockHeader *prevBlock(BlockHeader *header) const
    {
        if (header->prev_size == 0)
            return nullptr;
        return reinterpret_cast<BlockHeader *>(reinterpret_cast<char *>(header) - header->prev_size);
    }

    bool isValidBlock(BlockHeader *header) const
    {
        return (reinterpret_cast<char *>(header) >= m_pool &&
                reinterpret_cast<char *>(header) < (m_pool + m_poolSize));
    }

    void addToFreeList(FreeBlock *block)
    {
        block->next = m_freeList;
        block->prev = nullptr;
        if (m_freeList)
        {
            m_freeList->prev = block;
        }
        m_freeList = block;
    }

    void removeFromFreeList(FreeBlock *block)
    {
        if (block->prev)
        {
            block->prev->next = block->next;
        }
        else
        {
            m_freeList = block->next;
        }
        if (block->next)
        {
            block->next->prev = block->prev;
        }
        block->prev = block->next = nullptr;
    }
};